<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>第 7 节 递归函数的复杂度分析 | 算法不好玩</title>
    <meta name="generator" content="VuePress 1.8.2">
    <link rel="icon" href="/book/logo.png">
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.7.1/katex.min.css">
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/github-markdown-css/2.10.0/github-markdown.min.css">
    <meta name="description" content="">
    
    <link rel="preload" href="/book/assets/css/0.styles.e159a327.css" as="style"><link rel="preload" href="/book/assets/js/app.a4355b0d.js" as="script"><link rel="preload" href="/book/assets/js/2.ba785ee6.js" as="script"><link rel="preload" href="/book/assets/js/33.db835477.js" as="script"><link rel="prefetch" href="/book/assets/js/10.b6950be1.js"><link rel="prefetch" href="/book/assets/js/11.f4ee7d6e.js"><link rel="prefetch" href="/book/assets/js/12.50fe1ace.js"><link rel="prefetch" href="/book/assets/js/13.42356fcc.js"><link rel="prefetch" href="/book/assets/js/14.e740c742.js"><link rel="prefetch" href="/book/assets/js/15.05c628f7.js"><link rel="prefetch" href="/book/assets/js/16.bd9bc9d5.js"><link rel="prefetch" href="/book/assets/js/17.e120b4fc.js"><link rel="prefetch" href="/book/assets/js/18.398213f8.js"><link rel="prefetch" href="/book/assets/js/19.e29ad0b2.js"><link rel="prefetch" href="/book/assets/js/20.14e30c1c.js"><link rel="prefetch" href="/book/assets/js/21.4f05f6c9.js"><link rel="prefetch" href="/book/assets/js/22.98fbf199.js"><link rel="prefetch" href="/book/assets/js/23.285387f4.js"><link rel="prefetch" href="/book/assets/js/24.852addbe.js"><link rel="prefetch" href="/book/assets/js/25.d30ade13.js"><link rel="prefetch" href="/book/assets/js/26.23dfa040.js"><link rel="prefetch" href="/book/assets/js/27.b6eae7df.js"><link rel="prefetch" href="/book/assets/js/28.97878b08.js"><link rel="prefetch" href="/book/assets/js/29.7217a3d0.js"><link rel="prefetch" href="/book/assets/js/3.f0c15194.js"><link rel="prefetch" href="/book/assets/js/30.0ced5a5a.js"><link rel="prefetch" href="/book/assets/js/31.8f432033.js"><link rel="prefetch" href="/book/assets/js/32.aac9aa62.js"><link rel="prefetch" href="/book/assets/js/34.a1a59c2a.js"><link rel="prefetch" href="/book/assets/js/35.ed2ef96b.js"><link rel="prefetch" href="/book/assets/js/36.48099c55.js"><link rel="prefetch" href="/book/assets/js/37.32827612.js"><link rel="prefetch" href="/book/assets/js/38.58abec0e.js"><link rel="prefetch" href="/book/assets/js/39.f6eb3874.js"><link rel="prefetch" href="/book/assets/js/4.13ea3b32.js"><link rel="prefetch" href="/book/assets/js/40.80523ed8.js"><link rel="prefetch" href="/book/assets/js/41.f7b72b7a.js"><link rel="prefetch" href="/book/assets/js/42.44e40de9.js"><link rel="prefetch" href="/book/assets/js/43.065f077f.js"><link rel="prefetch" href="/book/assets/js/44.386d9aea.js"><link rel="prefetch" href="/book/assets/js/45.d8a88f16.js"><link rel="prefetch" href="/book/assets/js/46.33bc2083.js"><link rel="prefetch" href="/book/assets/js/47.e7767237.js"><link rel="prefetch" href="/book/assets/js/48.9bb76138.js"><link rel="prefetch" href="/book/assets/js/49.c2ca5c29.js"><link rel="prefetch" href="/book/assets/js/5.32eda204.js"><link rel="prefetch" href="/book/assets/js/50.1242fe24.js"><link rel="prefetch" href="/book/assets/js/51.e8f8117d.js"><link rel="prefetch" href="/book/assets/js/52.eae5648f.js"><link rel="prefetch" href="/book/assets/js/53.39876d83.js"><link rel="prefetch" href="/book/assets/js/6.1c662163.js"><link rel="prefetch" href="/book/assets/js/7.29470445.js"><link rel="prefetch" href="/book/assets/js/8.814b737f.js"><link rel="prefetch" href="/book/assets/js/9.d4211262.js">
    <link rel="stylesheet" href="/book/assets/css/0.styles.e159a327.css">
  </head>
  <body>
    <div id="app" data-server-rendered="true"><div class="theme-container no-sidebar"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/book/" class="home-link router-link-active"><!----> <span class="site-name">算法不好玩</span></a> <div class="links"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><a href="/book/" class="nav-link">
  主页
</a></div><div class="nav-item"><a href="/book/guide/" class="nav-link">
  关于我
</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="基础算法与数据结构" class="dropdown-title"><span class="title">基础算法与数据结构</span> <span class="arrow down"></span></button> <button type="button" aria-label="基础算法与数据结构" class="mobile-dropdown-title"><span class="title">基础算法与数据结构</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>
          排序算法
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/book/algs/01-binary-search/" class="nav-link">
  第 1 章 二分查找
</a></li><li class="dropdown-subitem"><a href="/book/algs/recursion/" class="nav-link router-link-active">
  第 2 章 递归
</a></li></ul></li><li class="dropdown-item"><h4>
          数组里的算法
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/book/algs/01-binary-search/" class="nav-link">
  第 4 章 滑动窗口
</a></li><li class="dropdown-subitem"><a href="/book/algs/02-basic-sorting/" class="nav-link">
  第 5 章 双指针
</a></li></ul></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="威威道来" class="dropdown-title"><span class="title">威威道来</span> <span class="arrow down"></span></button> <button type="button" aria-label="威威道来" class="mobile-dropdown-title"><span class="title">威威道来</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/book/talk-show/2021-04/" class="nav-link">
  2021 年 4 月
</a></li></ul></div></div><div class="nav-item"><a href="https://leetcode-cn.com/" target="_blank" rel="noopener noreferrer" class="nav-link external">
  力扣
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div><div class="nav-item"><a href="https://gitee.com/liweiwei1419/book/pages" target="_blank" rel="noopener noreferrer" class="nav-link external">
  Gitee 部署页面
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div> <!----></nav></div></header> <div class="sidebar-mask"></div> <aside class="sidebar"><nav class="nav-links"><div class="nav-item"><a href="/book/" class="nav-link">
  主页
</a></div><div class="nav-item"><a href="/book/guide/" class="nav-link">
  关于我
</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="基础算法与数据结构" class="dropdown-title"><span class="title">基础算法与数据结构</span> <span class="arrow down"></span></button> <button type="button" aria-label="基础算法与数据结构" class="mobile-dropdown-title"><span class="title">基础算法与数据结构</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>
          排序算法
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/book/algs/01-binary-search/" class="nav-link">
  第 1 章 二分查找
</a></li><li class="dropdown-subitem"><a href="/book/algs/recursion/" class="nav-link router-link-active">
  第 2 章 递归
</a></li></ul></li><li class="dropdown-item"><h4>
          数组里的算法
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/book/algs/01-binary-search/" class="nav-link">
  第 4 章 滑动窗口
</a></li><li class="dropdown-subitem"><a href="/book/algs/02-basic-sorting/" class="nav-link">
  第 5 章 双指针
</a></li></ul></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="威威道来" class="dropdown-title"><span class="title">威威道来</span> <span class="arrow down"></span></button> <button type="button" aria-label="威威道来" class="mobile-dropdown-title"><span class="title">威威道来</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/book/talk-show/2021-04/" class="nav-link">
  2021 年 4 月
</a></li></ul></div></div><div class="nav-item"><a href="https://leetcode-cn.com/" target="_blank" rel="noopener noreferrer" class="nav-link external">
  力扣
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div><div class="nav-item"><a href="https://gitee.com/liweiwei1419/book/pages" target="_blank" rel="noopener noreferrer" class="nav-link external">
  Gitee 部署页面
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div> <!----></nav>  <!----> </aside> <main class="page"> <div class="theme-default-content content__default"><h1 id="第-7-节-递归函数的复杂度分析"><a href="#第-7-节-递归函数的复杂度分析" class="header-anchor">#</a> 第 7 节 递归函数的复杂度分析</h1> <p>递归函数本质上是对树形结构或者图形结构的深度优先遍历。如果我们能够很清楚我们所设计的算法只访问了树形结构或者图形结构中的每个结点有限次，那么递归函数的时间复杂度就等于树形结构或者图形结构的结点个数。</p> <p>另外，分析递归函数的时间复杂读还有一个工具，称为「主定理」。由于「主定理」的理论性很强，只需要知道结论，会应用即可。在面试的时候，绝大多数情况下，不会考察主定理的内容和证明。我严谨的论述请参考《算法导论》第 4.5 节和第 4.6 节的内容。</p> <h2 id="主定理"><a href="#主定理" class="header-anchor">#</a> 主定理</h2> <p>如果一个规模为 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi></mjx-math></mjx-container> 的问题，可以拆解为 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="a"></mjx-c></mjx-mi></mjx-math></mjx-container> 个子问题，每个子问题的规模是 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mfrac><mjx-frac><mjx-num><mjx-nstrut></mjx-nstrut><mjx-mrow size="s"><mjx-mpadded><mjx-block style="margin:0.896em 0 0.313em;"><mjx-mrow></mjx-mrow></mjx-block></mjx-mpadded><mjx-mstyle style="font-size:141.4%;"><mjx-TeXAtom><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi></mjx-TeXAtom></mjx-mstyle></mjx-mrow></mjx-num><mjx-dbox><mjx-dtable><mjx-line></mjx-line><mjx-row><mjx-den><mjx-dstrut></mjx-dstrut><mjx-mrow size="s"><mjx-mpadded><mjx-block style="margin:0.896em 0 0.313em;"><mjx-mrow></mjx-mrow></mjx-block></mjx-mpadded><mjx-mstyle style="font-size:141.4%;"><mjx-TeXAtom><mjx-mi class="mjx-i"><mjx-c c="b"></mjx-c></mjx-mi></mjx-TeXAtom></mjx-mstyle></mjx-mrow></mjx-den></mjx-row></mjx-dtable></mjx-dbox></mjx-frac></mjx-mfrac></mjx-math></mjx-container>，其中 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="a"></mjx-c></mjx-mi><mjx-mo space="4" class="mjx-n"><mjx-c c="2265"></mjx-c></mjx-mo><mjx-mn space="4" class="mjx-n"><mjx-c c="1"></mjx-c></mjx-mn></mjx-math></mjx-container>，<mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="b"></mjx-c></mjx-mi><mjx-mo space="4" class="mjx-n"><mjx-c c="&gt;"></mjx-c></mjx-mo><mjx-mn space="4" class="mjx-n"><mjx-c c="1"></mjx-c></mjx-mn></mjx-math></mjx-container>。用 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="f"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo></mjx-math></mjx-container> 表示分解和合并的开销与 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi></mjx-math></mjx-container> 的关系，那么原始问题的时间复杂度 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="T"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo></mjx-math></mjx-container> 可以表示成如下递归式：</p>
T(n) = a \cdot T (\cfrac{n}{b}) + f(n)

<p>将此递推式得到关于 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi></mjx-math></mjx-container> 的通项公式的时候，需要利用以下结论：</p> <ul><li>如果 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="f"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo><mjx-mo space="4" class="mjx-n"><mjx-c c="&lt;"></mjx-c></mjx-mo><mjx-msup space="4"><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-script style="vertical-align:0.363em;"><mjx-TeXAtom size="s"><mjx-msub><mjx-mi noIC="true" class="mjx-n"><mjx-c c="l"></mjx-c><mjx-c c="o"></mjx-c><mjx-c c="g"></mjx-c></mjx-mi><mjx-script style="vertical-align:-0.241em;"><mjx-TeXAtom size="s"><mjx-mi class="mjx-i"><mjx-c c="b"></mjx-c></mjx-mi></mjx-TeXAtom></mjx-script></mjx-msub><mjx-mo class="mjx-n"><mjx-c c="2061"></mjx-c></mjx-mo><mjx-mi space="2" class="mjx-i"><mjx-c c="a"></mjx-c></mjx-mi></mjx-TeXAtom></mjx-script></mjx-msup></mjx-math></mjx-container>，那么 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="T"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo><mjx-mo space="4" class="mjx-n"><mjx-c c="="></mjx-c></mjx-mo><mjx-mi space="4" class="mjx-i"><mjx-c c="O"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-n"><mjx-c c="l"></mjx-c><mjx-c c="o"></mjx-c><mjx-c c="g"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="2061"></mjx-c></mjx-mo><mjx-mi space="2" class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo></mjx-math></mjx-container>；</li> <li>如果 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="f"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo><mjx-mo space="4" class="mjx-n"><mjx-c c="="></mjx-c></mjx-mo><mjx-msup space="4"><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-script style="vertical-align:0.363em;"><mjx-TeXAtom size="s"><mjx-msub><mjx-mi noIC="true" class="mjx-n"><mjx-c c="l"></mjx-c><mjx-c c="o"></mjx-c><mjx-c c="g"></mjx-c></mjx-mi><mjx-script style="vertical-align:-0.241em;"><mjx-TeXAtom size="s"><mjx-mi class="mjx-i"><mjx-c c="b"></mjx-c></mjx-mi></mjx-TeXAtom></mjx-script></mjx-msub><mjx-mo class="mjx-n"><mjx-c c="2061"></mjx-c></mjx-mo><mjx-mi space="2" class="mjx-i"><mjx-c c="a"></mjx-c></mjx-mi></mjx-TeXAtom></mjx-script></mjx-msup></mjx-math></mjx-container>，那么 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="T"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo><mjx-mo space="4" class="mjx-n"><mjx-c c="="></mjx-c></mjx-mo><mjx-mi space="4" class="mjx-i"><mjx-c c="O"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-msup><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-script style="vertical-align:0.363em;"><mjx-TeXAtom size="s"><mjx-msub><mjx-mi noIC="true" class="mjx-n"><mjx-c c="l"></mjx-c><mjx-c c="o"></mjx-c><mjx-c c="g"></mjx-c></mjx-mi><mjx-script style="vertical-align:-0.241em;"><mjx-TeXAtom size="s"><mjx-mi class="mjx-i"><mjx-c c="b"></mjx-c></mjx-mi></mjx-TeXAtom></mjx-script></mjx-msub><mjx-mo class="mjx-n"><mjx-c c="2061"></mjx-c></mjx-mo><mjx-mi space="2" class="mjx-i"><mjx-c c="a"></mjx-c></mjx-mi></mjx-TeXAtom></mjx-script></mjx-msup><mjx-mo space="3" class="mjx-n"><mjx-c c="22C5"></mjx-c></mjx-mo><mjx-mi space="3" class="mjx-n"><mjx-c c="l"></mjx-c><mjx-c c="o"></mjx-c><mjx-c c="g"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="2061"></mjx-c></mjx-mo><mjx-mi space="2" class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo></mjx-math></mjx-container>；</li> <li>如果 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="f"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo><mjx-mo space="4" class="mjx-n"><mjx-c c="&gt;"></mjx-c></mjx-mo><mjx-msup space="4"><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-script style="vertical-align:0.363em;"><mjx-TeXAtom size="s"><mjx-msub><mjx-mi noIC="true" class="mjx-n"><mjx-c c="l"></mjx-c><mjx-c c="o"></mjx-c><mjx-c c="g"></mjx-c></mjx-mi><mjx-script style="vertical-align:-0.241em;"><mjx-TeXAtom size="s"><mjx-mi class="mjx-i"><mjx-c c="b"></mjx-c></mjx-mi></mjx-TeXAtom></mjx-script></mjx-msub><mjx-mo class="mjx-n"><mjx-c c="2061"></mjx-c></mjx-mo><mjx-mi space="2" class="mjx-i"><mjx-c c="a"></mjx-c></mjx-mi></mjx-TeXAtom></mjx-script></mjx-msup></mjx-math></mjx-container>，那么 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="T"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo><mjx-mo space="4" class="mjx-n"><mjx-c c="="></mjx-c></mjx-mo><mjx-mi space="4" class="mjx-i"><mjx-c c="O"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-i"><mjx-c c="f"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo></mjx-math></mjx-container>。</li></ul> <p>证明过程请参考《算法导论》第 4.6 节（证明主定理）。结论可以这样记忆：</p> <p>比较 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="f"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo></mjx-math></mjx-container> 与 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-msup><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-script style="vertical-align:0.363em;"><mjx-TeXAtom size="s"><mjx-msub><mjx-mi noIC="true" class="mjx-n"><mjx-c c="l"></mjx-c><mjx-c c="o"></mjx-c><mjx-c c="g"></mjx-c></mjx-mi><mjx-script style="vertical-align:-0.241em;"><mjx-TeXAtom size="s"><mjx-mi class="mjx-i"><mjx-c c="b"></mjx-c></mjx-mi></mjx-TeXAtom></mjx-script></mjx-msub><mjx-mo class="mjx-n"><mjx-c c="2061"></mjx-c></mjx-mo><mjx-mi space="2" class="mjx-i"><mjx-c c="a"></mjx-c></mjx-mi></mjx-TeXAtom></mjx-script></mjx-msup></mjx-math></mjx-container> 的大小，如果相等，<mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="T"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo></mjx-math></mjx-container> 等于 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-msup><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-script style="vertical-align:0.363em;"><mjx-TeXAtom size="s"><mjx-msub><mjx-mi noIC="true" class="mjx-n"><mjx-c c="l"></mjx-c><mjx-c c="o"></mjx-c><mjx-c c="g"></mjx-c></mjx-mi><mjx-script style="vertical-align:-0.241em;"><mjx-TeXAtom size="s"><mjx-mi class="mjx-i"><mjx-c c="b"></mjx-c></mjx-mi></mjx-TeXAtom></mjx-script></mjx-msub><mjx-mo class="mjx-n"><mjx-c c="2061"></mjx-c></mjx-mo><mjx-mi space="2" class="mjx-i"><mjx-c c="a"></mjx-c></mjx-mi></mjx-TeXAtom></mjx-script></mjx-msup></mjx-math></mjx-container> 后面乘以 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-n"><mjx-c c="l"></mjx-c><mjx-c c="o"></mjx-c><mjx-c c="g"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="2061"></mjx-c></mjx-mo><mjx-mi space="2" class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi></mjx-math></mjx-container>。如果不相等，谁大就以谁作为时间复杂度，这一点与「时间复杂度考虑最差情况」的规则一致。</p> <h3 id="例-1-使用主定理计算「二分查找」的时间复杂度"><a href="#例-1-使用主定理计算「二分查找」的时间复杂度" class="header-anchor">#</a> 例 1：使用主定理计算「二分查找」的时间复杂度</h3> <p>二分查找每一次将问题一分为二，但是只在其中一个子问题里继续求解，此时 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="a"></mjx-c></mjx-mi><mjx-mo space="4" class="mjx-n"><mjx-c c="="></mjx-c></mjx-mo><mjx-mn space="4" class="mjx-n"><mjx-c c="1"></mjx-c></mjx-mn></mjx-math></mjx-container>，<mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="b"></mjx-c></mjx-mi><mjx-mo space="4" class="mjx-n"><mjx-c c="="></mjx-c></mjx-mo><mjx-mn space="4" class="mjx-n"><mjx-c c="2"></mjx-c></mjx-mn></mjx-math></mjx-container>。只有拆分子问题，不用合并子问题，此时 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="f"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo><mjx-mo space="4" class="mjx-n"><mjx-c c="="></mjx-c></mjx-mo><mjx-mn space="4" class="mjx-n"><mjx-c c="1"></mjx-c></mjx-mn></mjx-math></mjx-container>（常数次操作，与 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi></mjx-math></mjx-container> 无关）。比较 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-msup><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-script style="vertical-align:0.363em;"><mjx-TeXAtom size="s"><mjx-msub><mjx-mi noIC="true" class="mjx-n"><mjx-c c="l"></mjx-c><mjx-c c="o"></mjx-c><mjx-c c="g"></mjx-c></mjx-mi><mjx-script style="vertical-align:-0.241em;"><mjx-TeXAtom size="s"><mjx-mi class="mjx-i"><mjx-c c="b"></mjx-c></mjx-mi></mjx-TeXAtom></mjx-script></mjx-msub><mjx-mo class="mjx-n"><mjx-c c="2061"></mjx-c></mjx-mo><mjx-mi space="2" class="mjx-i"><mjx-c c="a"></mjx-c></mjx-mi></mjx-TeXAtom></mjx-script></mjx-msup><mjx-mo space="4" class="mjx-n"><mjx-c c="="></mjx-c></mjx-mo><mjx-msup space="4"><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-script style="vertical-align:0.363em;"><mjx-TeXAtom size="s"><mjx-msub><mjx-mi noIC="true" class="mjx-n"><mjx-c c="l"></mjx-c><mjx-c c="o"></mjx-c><mjx-c c="g"></mjx-c></mjx-mi><mjx-script style="vertical-align:-0.241em;"><mjx-TeXAtom size="s"><mjx-mn class="mjx-n"><mjx-c c="2"></mjx-c></mjx-mn></mjx-TeXAtom></mjx-script></mjx-msub><mjx-mo class="mjx-n"><mjx-c c="2061"></mjx-c></mjx-mo><mjx-mn space="2" class="mjx-n"><mjx-c c="1"></mjx-c></mjx-mn></mjx-TeXAtom></mjx-script></mjx-msup><mjx-mo space="4" class="mjx-n"><mjx-c c="="></mjx-c></mjx-mo><mjx-msup space="4"><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-script style="vertical-align:0.363em;"><mjx-TeXAtom size="s"><mjx-mn class="mjx-n"><mjx-c c="0"></mjx-c></mjx-mn></mjx-TeXAtom></mjx-script></mjx-msup><mjx-mo space="4" class="mjx-n"><mjx-c c="="></mjx-c></mjx-mo><mjx-mn space="4" class="mjx-n"><mjx-c c="1"></mjx-c></mjx-mn></mjx-math></mjx-container>，套用主定理的第二种情况，此时 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="T"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo><mjx-mo space="4" class="mjx-n"><mjx-c c="="></mjx-c></mjx-mo><mjx-mi space="4" class="mjx-i"><mjx-c c="O"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-n"><mjx-c c="l"></mjx-c><mjx-c c="o"></mjx-c><mjx-c c="g"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="2061"></mjx-c></mjx-mo><mjx-mi space="2" class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo></mjx-math></mjx-container>。</p> <h3 id="例-2-根据主定理推导「归并排序」的时间复杂度"><a href="#例-2-根据主定理推导「归并排序」的时间复杂度" class="header-anchor">#</a> 例 2：根据主定理推导「归并排序」的时间复杂度</h3> <p>二分查找每一次将问题一分为二，然后递归在两个子问题里继续求解，此时 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="a"></mjx-c></mjx-mi><mjx-mo space="4" class="mjx-n"><mjx-c c="="></mjx-c></mjx-mo><mjx-mn space="4" class="mjx-n"><mjx-c c="2"></mjx-c></mjx-mn></mjx-math></mjx-container>，<mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="b"></mjx-c></mjx-mi><mjx-mo space="4" class="mjx-n"><mjx-c c="="></mjx-c></mjx-mo><mjx-mn space="4" class="mjx-n"><mjx-c c="2"></mjx-c></mjx-mn></mjx-math></mjx-container>。拆分子问题使用了 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="O"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mn class="mjx-n"><mjx-c c="1"></mjx-c></mjx-mn><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo></mjx-math></mjx-container>，合并子问题使用了 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="f"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo><mjx-mo space="4" class="mjx-n"><mjx-c c="="></mjx-c></mjx-mo><mjx-mi space="4" class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi></mjx-math></mjx-container>，此时 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="f"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo><mjx-mo space="4" class="mjx-n"><mjx-c c="="></mjx-c></mjx-mo><mjx-mi space="4" class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi></mjx-math></mjx-container>。比较 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-msup><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-script style="vertical-align:0.363em;"><mjx-TeXAtom size="s"><mjx-msub><mjx-mi noIC="true" class="mjx-n"><mjx-c c="l"></mjx-c><mjx-c c="o"></mjx-c><mjx-c c="g"></mjx-c></mjx-mi><mjx-script style="vertical-align:-0.241em;"><mjx-TeXAtom size="s"><mjx-mi class="mjx-i"><mjx-c c="b"></mjx-c></mjx-mi></mjx-TeXAtom></mjx-script></mjx-msub><mjx-mo class="mjx-n"><mjx-c c="2061"></mjx-c></mjx-mo><mjx-mi space="2" class="mjx-i"><mjx-c c="a"></mjx-c></mjx-mi></mjx-TeXAtom></mjx-script></mjx-msup><mjx-mo space="4" class="mjx-n"><mjx-c c="="></mjx-c></mjx-mo><mjx-msup space="4"><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-script style="vertical-align:0.363em;"><mjx-TeXAtom size="s"><mjx-msub><mjx-mi noIC="true" class="mjx-n"><mjx-c c="l"></mjx-c><mjx-c c="o"></mjx-c><mjx-c c="g"></mjx-c></mjx-mi><mjx-script style="vertical-align:-0.241em;"><mjx-TeXAtom size="s"><mjx-mn class="mjx-n"><mjx-c c="2"></mjx-c></mjx-mn></mjx-TeXAtom></mjx-script></mjx-msub><mjx-mo class="mjx-n"><mjx-c c="2061"></mjx-c></mjx-mo><mjx-mn space="2" class="mjx-n"><mjx-c c="2"></mjx-c></mjx-mn></mjx-TeXAtom></mjx-script></mjx-msup><mjx-mo space="4" class="mjx-n"><mjx-c c="="></mjx-c></mjx-mo><mjx-mi space="4" class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi></mjx-math></mjx-container>，套用主定理的第二种情况，此时 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mi class="mjx-i"><mjx-c c="T"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo><mjx-mo space="4" class="mjx-n"><mjx-c c="="></mjx-c></mjx-mo><mjx-mi space="4" class="mjx-i"><mjx-c c="O"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="("></mjx-c></mjx-mo><mjx-mi class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-mi space="2" class="mjx-n"><mjx-c c="l"></mjx-c><mjx-c c="o"></mjx-c><mjx-c c="g"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c="2061"></mjx-c></mjx-mo><mjx-mi space="2" class="mjx-i"><mjx-c c="n"></mjx-c></mjx-mi><mjx-mo class="mjx-n"><mjx-c c=")"></mjx-c></mjx-mo></mjx-math></mjx-container>。</p></div> <footer class="page-edit"><!----> <!----></footer> <!----> </main></div><div class="global-ui"><!----></div></div>
    <script src="/book/assets/js/app.a4355b0d.js" defer></script><script src="/book/assets/js/2.ba785ee6.js" defer></script><script src="/book/assets/js/33.db835477.js" defer></script>
  </body>
</html>
